Comprehension - Sieve of Eratosthenes

Sieve of Eratosthenes

N = 100
no_primes = [j for i in range(2, 8) for j in range(i * 2, N, i)]
primes = [x for x in range(2, N) if x not in no_primes]

print(primes)

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Use set comprehension

from math import sqrt

N = 100
sqrt_n = int(sqrt(N))
no_primes = {j for i in range(2, sqrt_n + 1) for j in range(i * 2, N, i)}
primes = {x for x in range(2, N) if x not in no_primes}

print(primes)

with recursion

from math import sqrt

def primes(N):
    if N == 0:
        return []
    elif N == 1:
        return []
    else:
        p = primes(int(sqrt(N)))
        no_primes = {j for i in p for j in range(i * 2, N + 1, i)}
        p = {x for x in range(2, N + 1) if x not in no_primes}
    return p

for i in range(1, 50):
    print(i, primes(i))

Output:

1 []
2 {2}
3 {2, 3}
4 {2, 3}
5 {2, 3, 5}
6 {2, 3, 5}
7 {2, 3, 5, 7}
8 {2, 3, 5, 7}
9 {2, 3, 5, 7}
10 {2, 3, 5, 7}
11 {2, 3, 5, 7, 11}
12 {2, 3, 5, 7, 11}
13 {2, 3, 5, 7, 11, 13}
14 {2, 3, 5, 7, 11, 13}
15 {2, 3, 5, 7, 11, 13}
16 {2, 3, 5, 7, 11, 13}
17 {2, 3, 5, 7, 11, 13, 17}
18 {2, 3, 5, 7, 11, 13, 17}
19 {2, 3, 5, 7, 11, 13, 17, 19}
20 {2, 3, 5, 7, 11, 13, 17, 19}
21 {2, 3, 5, 7, 11, 13, 17, 19}
22 {2, 3, 5, 7, 11, 13, 17, 19}
23 {2, 3, 5, 7, 11, 13, 17, 19, 23}
24 {2, 3, 5, 7, 11, 13, 17, 19, 23}
. . .
43 {2, 3, 5, 37, 7, 41, 11, 43, 13, 17, 19, 23, 29, 31}
44 {2, 3, 5, 37, 7, 41, 11, 43, 13, 17, 19, 23, 29, 31}
45 {2, 3, 5, 37, 7, 41, 11, 43, 13, 17, 19, 23, 29, 31}
46 {2, 3, 5, 37, 7, 41, 11, 43, 13, 17, 19, 23, 29, 31}
47 {2, 3, 5, 37, 7, 41, 11, 43, 13, 47, 17, 19, 23, 29, 31}
48 {2, 3, 5, 37, 7, 41, 11, 43, 13, 47, 17, 19, 23, 29, 31}
49 {2, 3, 5, 37, 7, 41, 11, 43, 13, 47, 17, 19, 23, 29, 31}